/**
 * https://leetcode.com/problems/merge-two-sorted-lists/?envType=study-plan-v2&envId=top-interview-150
 *
 * You are given the heads of two sorted linked lists list1 and list2.
 *
 * Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
 *
 * Return the head of the merged linked list.
 *
 * Example 1:
 * Input: list1 = [1,2,4], list2 = [1,3,4]
 * Output: [1,1,2,3,4,4]
 *
 * Example 2:
 * Input: list1 = [], list2 = []
 * Output: []
 *
 * Example 3:
 * Input: list1 = [], list2 = [0]
 * Output: [0]
 *
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
        val temp = ListNode(0)
        var current = temp
        var l1 = list1
        var l2 = list2

        while (l1 != null && l2 != null) {
            if (l1.`val` <= l2.`val`) {
                current.next = l1
                l1 = l1.next
            } else {
                current.next = l2
                l2 = l2.next
            }
            current = current.next
        }

        current.next = l1 ?: l2

        return temp.next
    }

    // fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
    //     var list = mutableListOf<Int>()
    //     var list1 = list1
    //     var list2 = list2
    //
    //     while (true) {
    //         if (list1 == null) break
    //         list.add(list1.`val`)
    //         list1 = list1.next
    //     }
    //
    //     while (true) {
    //         if (list2 == null) break
    //         list.add(list2.`val`)
    //         list2 = list2.next
    //     }
    //
    //     if (list.isEmpty()) return null
    //     list.sortDescending()
    //
    //     var newHead = ListNode(list[0])
    //
    //     for (i in 1 until list.size) {
    //         val newNode = ListNode(list[i])
    //         newNode.next = newHead
    //         newHead = newNode
    //     }
    //     return newHead
    // }
}